class ImmutableListNode(object):
    def printValue(self):  # print the value of this node.
        """
        :rtype None
        """

    def getNext(self):  # return the next node.
        """
        :rtype ImmutableListNode
        """


import collections


# # 线性时间空间
# class Solution(object):
#     def printLinkedListInReverse(self, head):
#         """
#         :type head: ImmutableListNode
#         :rtype: None
#         """
#         out = collections.deque()
#         while head.getNext():
#             out.append(head)
#             head = head.getNext()
#         out.append(head)
#         out.reverse()
#         for node in out:
#             node.printValue()


# 线性时间，对数空间
class Solution(object):
    def printLinkedListInReverse(self, head):
        """
        :type head: ImmutableListNode
        :rtype: None
        """
        node = head
        n = 1
        while node.getNext():
            n += 1
            node = node.getNext()

        def search(node, n):
            if n == 1:
                node.printValue()
            else:
                mid_n = n // 2
                index = 0
                mid_node = node
                while index < mid_n:
                    mid_node = mid_node.getNext()
                search(mid_node, n - mid_n)
                search(node, mid_n)

        search(head, n)
